//
// Created by hay boy on 2022/7/5.
//

#ifndef ALGORITHMS_ARRAYDEQUE_H
#define ALGORITHMS_ARRAYDEQUE_H
#include "Queue.h"
#include "QueueException.h"
#include "../exception/illegalParameterValue.h"
#include <sstream>
template<class T>
class ArrayDeque : public Queue<T> {
private:
    int theFront;
    int theBack;
    int arrayLength;
    T* queue;
public:
    explicit ArrayDeque(int initialCapacity=10);
    ~ArrayDeque(){
        delete []queue;
    }
    bool empty() const{
        return theFront == theBack;
    }
    int size() const{
        return (theBack-theFront+arrayLength)%arrayLength;
    }
    T& front(){
        if(theFront==theBack){
            throw QueueEmpty();
        }
        return queue[(theFront+1)%arrayLength];
    }
    T& back(){
        if(theFront==theBack){
            throw QueueEmpty();
        }
        return queue[theBack];
    }
    void pop(){
        pop_front();
    }
    void push(const T& theElement){
        push_back(theElement);
    }
    virtual void clear();
    virtual void push_front(const T& theElement);
    virtual void push_back(const T& theElement);
    virtual void pop_front();
    virtual void pop_back();

};

template<class T>
ArrayDeque<T>::ArrayDeque(int initialCapacity) {
    if(initialCapacity<1){
        ostringstream s;
        s<<"Initial capacity = "<<initialCapacity<<" Must be > 0 ";
        throw illegalParameterValue(s.str());
    }
    arrayLength = initialCapacity;
    queue = new T[arrayLength];
    theFront = 0;
    theBack = 0;
}

template<class T>
void ArrayDeque<T>::clear() {
    if(theFront>theBack){
        for(int i = theFront+1;i<=arrayLength-1;i++){
            queue[i].~T();
        }
        for(int i = 0;i<=theBack;i++){
            queue[i].~T();
        }
    }else{
        for(int i = theFront+1;i<=theBack;i++){
            queue[i].~T();
        }
    }
    theFront = theBack = 0;
}

template<class T>
void ArrayDeque<T>::push_front(const T& theElement) {
    const int newFront = theFront==0?arrayLength-1:theFront-1;
    if(newFront==theBack){
        T* newQueue = new T[2*arrayLength];
        int start = (theFront+1)%arrayLength;
        newQueue[0] = theElement;
        if(start<2){
            copy(queue+start,queue+start+arrayLength-1,newQueue+1);
        }else{
            copy(queue+start,queue+arrayLength,newQueue+1);
            copy(queue,queue+theBack+1,newQueue+arrayLength-start+1);
        }
    }
    queue[theFront] = theElement;
    theFront = newFront;
}

template<class T>
void ArrayDeque<T>::push_back(const T&theElement) {
    if((theBack+1)%arrayLength==theFront){
        T* newQueue = new T[2*arrayLength];
        int start = (theFront+1)%arrayLength;
        if(start<2){
            copy(queue+start,queue+start+arrayLength-1,newQueue);
        }else{
            copy(queue+start,queue+arrayLength,newQueue);
            copy(queue,queue+theBack+1,newQueue+arrayLength-start);
        }
        theFront = 2 * arrayLength - 1;
        theBack = arrayLength - 2;
        arrayLength *= 2;
        queue = newQueue;
    }
    theBack = (theBack+1)%arrayLength;
    queue[theBack] = theElement;
}

template<class T>
void ArrayDeque<T>::pop_front() {
    if(theFront==theBack){
        throw QueueEmpty();
    }
    theFront = (theFront+1)%arrayLength;
    queue[theFront].~T();
}

template<class T>
void ArrayDeque<T>::pop_back() {
    if(theFront==theBack){
        throw QueueEmpty();
    }
    queue[theBack].~T();
    if(theBack==0){//-1%8==-1!=7,所以要采用这种那个方式来决定新的theBack
        theBack = arrayLength - 1;
    }else{
        theBack--;
    }
}


#endif //ALGORITHMS_ARRAYDEQUE_H
